package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 953. 验证外星语词典
 *
 * 2022-05-17 每日一题
 *
 * @author fy
 * @date 2022/5/17 8:05
 */
public class Solution953 {

    public boolean isAlienSorted(String[] words, String order) {
        // 使用map记录字符对应排序位置
        Map<Character, Integer> map = new HashMap<>(order.length());
        map.put('∅', -1);
        for (int i = 0; i < order.length(); i++) {
            map.put(order.charAt(i), i);
        }
        for (int i = 1; i < words.length; i++) {
            String word1 = words[i - 1];
            String word2 = words[i];

            int len1 = word1.length();
            int len2 = word2.length();
            int idx = 0;
            while (idx < len1 || idx < len2) {
                char ch1 = idx < len1 ? word1.charAt(idx) : '∅';
                char ch2 = idx < len2 ? word2.charAt(idx) : '∅';
                if (map.get(ch2) - map.get(ch1) < 0) {
                    return false;
                } else if (map.get(ch2) - map.get(ch1) > 0) {
                    break;
                }
                idx++;
            }
        }
        return true;
    }

}
